

# 变量，标量解释=====================================================================================================
# s：原字符串，处理后的字符串
# p: 回文半径数组
# i: 当前下标
# center, r: r 最远的回文覆盖位置以center为中心(不包含r位置)， center 最远的回文半径的中心
#                   两者同步更新
# i': i 相对于center 的对称位置
# radius: i位置的回文半径长度包括i位置，即多算了长度+1
# result解释=======================================================================================================
# 对应原字符串回文长度: p[i] - 1， 如果原本回文长度是偶数的话则是#扩出来的则半径-中间那个#；
#                                   如果原本回文长度是奇数则一定扩到#，减去最后那个#
# 核心流程==========================================================================================================
# * 匹配加速：
#   1）i突破了之前的r，那就老实的匹配
#   2）i被r保包住,如果i'在以c为中心的回文半径内，则i的回文半径直接等于i'的回文半径。    (对称性)
#   3）i被r保包住,如果i'在以c为中心的回文半径外，则i的回文半径直接等于r-i的回文半径。   (对称性)
#   4）i被r保包住,如果i'在以c为中心的回文半径上，则i的回文半径至少为i'的回文半径，但可能更长。   (对称性)
# 情况如上并不复杂，但如何编写简短地代码？是一个问题
def manacher(s: str) -> int:
    s = '#' + '#'.join(s) + '#'
    n = len(s)
    p = [1] * n
    i, center, r = 0, 0, 0
    while i < n:
        i_prime = 2 * center - i
        # 涵盖1,2,3,4。无非就是2,3的情况多进行了一次无用的比较而已。但使得代码简洁了许多，少了很多if
        radius = min(p[i_prime], r - i) if r > i else 1
        while 0 <= i - radius and i + radius < n and s[i - radius] == s[i + radius]:
            radius += 1
        if i + radius > r:
            center, r = i, i + radius
        p[i] = radius
        i += 1
    return max(p) - 1


if __name__ == '__main__':
    s = 'dabaabac'
    print(manacher(s))
